A source program of software code may be manipulated by a computer compiler, and the compiler may include an optimizer that produces object code that executes faster and consumes less computer memory than object code produced by a compiler without an optimizer. Many compiler optimizers have been designed to execute instructions in a prescribed format that is predictable and therefore can be easily manipulated. One such format is single static assignment (SSA) form which requires that each variable in a transformed program is defined in only one definition statement.
A control flow graph (CFG) represents the flow of control of program code, where each node represents a basic block and each edge shows a possible path for the flow of control between basic blocks. A basic block has a single entry instruction and a single exit instruction that is defined by a branch instruction. If the first instruction in the basic block is executed, all other instructions in the basic block will be executed. A basic block may also consist of a single instruction. A CFG has a unique source node which is called an entry node.
A node with more than one successor is a branch node or a split node, and a node with more than one predecessor is a join node. For instance, a node will have multiple successors for conditional branches. A node n.sub.1 dominates another node n.sub.2 if every possible execution path from the entry to n.sub.2 contains n.sub.1. The flow of control of a loop may be described by the edges of the loop in which the edge has a head node and a tail node, and the head node dominates the tail node.
FIG. 1A illustrates a CFG 100 depicting the intermediate representation of a source program. A variable is defined when it is assigned a value, and it is used when it accessed without changing the value. Therefore, in FIG. 1A the variable x is defined in nodes 102 and 104, and is used in nodes 106 and 108. Further, since the variable x is defined more than once, the intermediate representation is not in SSA form.
When several names of a variable, x.sub.1, X.sub.2. . . x.sub.n reach a join node in a control flow graph, a phi (.PHI.) function assignment statement x.sub.m =.PHI.(x.sub.1, x.sub.2. . . x.sub.n) may be inserted to merge the names into the definition of a new name, x.sub.m and therefore, x.sub.m is defined in only one definition statement, thus preserving the SSA form.
FIG. 1B shows the CFG 100 in SSA form. In order to transform the intermediate code depicted in FIG. 1A, in FIG. 1B the variable x has been renamed. The first name for the variable x is x.sub.1 as shown in node 102. All uses are appropriately renamed to match the new name for the variable x so that the value flow from the variable's definition to its use(s) is explicitly apparent in the program text. For instance, x.sub.1 is the name of the use of the variable x in node 106. The second name for the variable x is x.sub.2 as shown in node 104. The third name for the variable x is x.sub.3 as shown in node 108. The phi-function .PHI.(x.sub.1, x.sub.2) merges the x.sub.1 and the x.sub.2 names of the variable x into one definition statement for x.sub.3, x.sub.3 =.PHI.(x.sub.1, x.sub.2). The phi-function in node 108 can be reached from either node 102 or node 104 and also satisfies the requirements of SSA form. The original variable x now is represented by three names, x.sub.1, x.sub.2, and x.sub.3.
Most optimization procedures require SSA form to ensure efficient optimization processing. Loop unrolling is such an optimization procedure and is produced by a method of replicating a loop during the process of compilation. However, loop unrolling can alter the code such that it is no longer in SSA form. That is, when a variable is renamed to satisfy SSA form requirements, the effects of loop unrolling must be considered and each new name for each unrolled loop iteration must be unique. Applying incremental update techniques such as SSA form along with loop unrolling are very difficult, as the effects of loop unrolling create many new names that are associated with the incarnations of the unrolled loop, and these new names must all be translated into SSA form. Most compiler technologies do not attempt loop unrolling updates and incremental SSA form updates in the same compiler cycle (hereinafter called a "compiler pass"). Rather, most compiler technologies compute the updated names in SSA form afresh after loop unrolling and do not attempt resource intensive incremental updates to translate the names into SSA form. There is therefore a need in the art to overcome this problem.